package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.List;

/**
 * Prime算法(即时实现)构造最小生成树
 * 断寻找权重最小的横切边加入生成树中，最终生成的生成树即为最小生成树。
 * 
 * 空间复杂度O(V)，时间复杂度O(ElogV)
 * @author 付大石
 */
public class DiligentPrim {

    public static void main(String[] args) {

        UndirectedGraph g = new UndirectedGraph(8);
        g.addEdge(new Edge(4, 5, 0.35));
        g.addEdge(new Edge(4, 7, 0.37));
        g.addEdge(new Edge(5, 7, 0.28));
        g.addEdge(new Edge(0, 7, 0.16));
        g.addEdge(new Edge(1, 5, 0.32));
        g.addEdge(new Edge(0, 4, 0.38));
        g.addEdge(new Edge(2, 3, 0.17));
        g.addEdge(new Edge(1, 7, 0.19));
        g.addEdge(new Edge(0, 2, 0.26));
        g.addEdge(new Edge(1, 2, 0.36));
        g.addEdge(new Edge(1, 3, 0.29));
        g.addEdge(new Edge(2, 7, 0.34));
        g.addEdge(new Edge(6, 2, 0.40));
        g.addEdge(new Edge(3, 6, 0.52));
        g.addEdge(new Edge(6, 0, 0.58));
        g.addEdge(new Edge(6, 4, 0.93));
        for (Edge edge : new DiligentPrim(g).edges()) {
            System.out.println(edge);
        }
    }

    private Edge[] edgeTo;
    private double[] distTo;
    private boolean[] marked;
    private IndexMinPQ<Double> indexPQ;

    public DiligentPrim(UndirectedGraph g) {

        // 初始化数据域 //
        int v = g.v();
        edgeTo = new Edge[v];
        distTo = new double[v];
        for (int i = 0; i < distTo.length; i++) {
            distTo[i] = Double.MAX_VALUE;
        }
        marked = new boolean[v];
        indexPQ = new IndexMinPQ<>(v);

        // 构造minimum spanning tree //
        distTo[0] = 0;
        indexPQ.insert(0, 0.0); // 用顶点0初始化索引优先队列
        while (!indexPQ.isEmpty()) {
            visit(g, indexPQ.delMin());
        }
        if (!check(g)) {
            throw new RuntimeException("失败，生成的不是最小生成树");
        }
    }

    private void visit(UndirectedGraph g, int v) {

        marked[v] = true;
        for (Edge edge : g.adj(v)) {
            int w = edge.other(v);
            if (marked[w]) {
                continue;
            }
            if (edge.weight() < distTo[w]) {
                distTo[w] = edge.weight();
                edgeTo[w] = edge;
                indexPQ.insert(w, edge.weight());
            }
        }
    }

    public Iterable<Edge> edges() {

        List<Edge> list = new ArrayList<>();
        for (int i = 0; i < edgeTo.length; i++) {
            if (edgeTo[i] != null) {
                list.add(edgeTo[i]);
            }
        }
        return list;
    }

    public double weight() {

        double weight = 0;
        for (Edge edge : edges()) {
            weight += edge.weight();
        }
        return weight;
    }

    /**
     * 检测生成的MST是否正确
     * @return
     */
    private boolean check(UndirectedGraph g) {

        // 检测是否有环，有环则不是MST //
        UnionFind uf = new UnionFind(g.v());
        for (Edge e : edges()) {
            int v = e.either();
            int w = e.other(v);
            if (uf.connected(v, w)) {
                return false;
            }
            uf.union(v, w);
        }

        // 检测是否是一棵树还是多课树，多棵树则不是MST //
        if (uf.count() != 1) {
            return false;
        }

        // 检测是否是最小生成树 //
        for (Edge e : edges()) {
            uf = new UnionFind(g.v());
            for (Edge f : edges()) {
                if (f != e) {
                    int v = f.either();
                    int w = f.other(v);
                    uf.union(v, w);
                }
            }
            for (Edge f : g.edges()) {
                int v = f.either();
                int w = f.other(v);
                if (!uf.connected(v, w)) {
                    if (f.weight() < e.weight()) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
